/*
 * Author: Wang Hsutung
 * Date: 2015/11/06
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */

#include <iostream>
#include <vector>

using namespace std;

typedef std::vector<unsigned int> ulist;
unsigned int count = 0;

inline void printlist(ulist v)
{
    for (size_t i = 0; i < v.size(); ++i)
        cout << v[i] << " ";
}

void arrageNum(unsigned int n, const ulist &v)
{
    if (n == 0) {
        cout << "(" << ++count << "). ";
        printlist(v);
        cout << endl;
        return;
    }

    for (size_t i = 0; i + n + 1 < v.size(); ++i) {
        if (v[i] || v[i + n + 1])
            continue;
        ulist dup(v);
        dup[i] = dup[i + n + 1] = n;
        arrageNum(n - 1, dup);
    }
}

void showSolution(unsigned int n)
{
    ulist state(2 * n, 0);
    arrageNum(n, state);
    cout << (count > 0 ? "Done" : "No solution") 
        << " for number " << n << " ! "<< endl;
}

int main(int argc, char *argv[])
{
    unsigned int n;
    cout << "Input a integer > 0, this program will give all "
        << "possibilities of combination of 1,1,2,2,...,n,n "
        << "(2n numbers altogether) that satisfies there are"
        << " n numbers between each n pair.\n\n  n = ";
    cin >> n;
    showSolution(n);
    return(0);
}
